from typing import List


def merge(nums1: List[int], nums2: List[int]) -> List[int]:
    result = []
    while len(nums1) > 0 and len(nums2) > 0:
        if nums1[0] <= nums2[0]:
            result.append(nums1.pop(0))
        else:
            result.append(nums2.pop(0))
    while len(nums1) > 0:
        result.append(nums1.pop(0))
    while len(nums2) > 0:
        result.append(nums2.pop(0))
    return result


def sort_array(nums: List[int]) -> List[int]:
    if len(nums) < 2:
        return nums
    middle = len(nums) // 2
    left = nums[:middle]
    right = nums[middle:]
    return merge(sort_array(left), sort_array(right))


def merge_sort(array1: List[int], array2: List[int], array3: List[int], array4: List[int]) -> List[int]:
    array1 = sort_array(array1)
    array2 = sort_array(array2)
    array3 = sort_array(array3)
    array4 = sort_array(array4)

    array = merge(array1, array2)
    array = merge(array, array3)
    array = merge(array, array4)
    return array


if __name__ == '__main__':
    array1 = [0, 4, 8, 4, 9, 10, 32, 44, 56]
    array2 = [13, 2, 33, 48, 51, 15, 17, 77]
    array3 = [12, 1, 30, 46, 7, 11, 16, 29]
    array4 = [14, 18, 27, 23, 56, 100, 101, 5]
    print(merge_sort(array1, array2, array3, array4))